from typing import List

# 219. 存在重复元素 II
# 时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次，对于每个元素，哈希表的操作时间都是 O(1)。
#
# 空间复杂度：O(n)，n nnn 是数组 nums 的长度。需要使用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超过 n。
def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    # hashtable 中保存上一次出现num的index
    num_dict = {}
    re = False
    for index, value in enumerate(nums):
        last_index = num_dict.get(value)
        if last_index is None:
            num_dict[value] = index
        else:
            if (index - last_index) <= k:
                re = True
                break
            else:
                num_dict[value] = index

    return re


nums = [1, 2, 3, 1]
k = 3
result = containsNearbyDuplicate(nums, k)
print(f"result:{result}")

nums = [1, 0, 1, 1]
k = 1
result = containsNearbyDuplicate(nums, k)
print(f"result:{result}")

nums = [1, 2, 3, 1, 2, 3]
k = 2
result = containsNearbyDuplicate(nums, k)
print(f"result:{result}")
